Networks are the simplest form of representation of the interactions between real world objects. Most of these real world networks exhibit the property of community structure, i.e. nodes in the network can be partitioned into groups such that more edges are present between nodes belonging to the same group than between the nodes belonging to different groups.
This structural property is important as the groups in the networks correspond to a real world property of the network. For example, groups can exist based on interests, ethnicity, location and social behavior in a telecommunications call graph network, users grouped based on favorite shopping/hangout destinations using a mobility graph, and so on.
The structural properties of groups or communities can be used for a variety of applications, such as recommending services, pushing advertisements to certain users, customizing schemes, finding alpha users within a community to increase up-selling, finding an influence circle of a user, which can be used for recommender systems, and so on. It is also relevant to other domains, for example, identifying research area in a collaboration network, or grouping related pages in World Wide Web.
Community detection algorithms have been developed to detect the presence of communities or groups in a network. Different types of algorithms exist, including ones that perform a divisive, agglomerative or maximization of an objective function.
Many different scoring functions exist for use by community detecting algorithms. Modularity is a term used for one such popular scoring function (an objective function) which quantifies the quality of communities. Finding communities by maximization of modularity is a widely used method. One such example is a so-called Louvain method which greedily maximizes modularity, and is currently one of the fastest algorithms to find communities within a network. Further details of this method are discussed in a paper entitled “Fast unfolding of communities in large networks”, by Vincent D. Blondel, et al, Journal of Statistical Mechanics, 2008, arXiv:0803.0476.
A disadvantage of modularity is that it suffers from resolution limit. A paper entitled “Resolution limit in a community detection” by Santo Fortunato, et al, Proceedings of the National Academy of Sciences of the United States of America (PNAS), vol. 104, no. 01, January 2007, discusses how modularity optimization can fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined. In other words, modularity cannot find small communities in a large network. For instance in a mobility graph, if there are two close groups (with high interactions), if a user A belongs to group 1 and user B belongs to group 2, even if user A and B have less common interests but are connected, then a modularity based method would combine these two communities into one community.
Furthermore, other techniques such as the divisive technique or agglomerative technique are not scalable, as discussed in US2008/0313251A1 and US2013/0198191A1.